COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\rm
C00004 ENDMK
C⊗;
\rm
\magnification=\magstephalf

\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}

\line{\sevenrm A01.tex[154,rwf] \today\hfill}

\vskip 1in

\noindent
Question:

How many generators are required to get, by composition, all the functions
on $\{1,2,\ldots ,n\}$? 

\vskip .125in

\noindent
Answer:

3 are necessary and sufficient for $n≥3$; $f(x)=1$ and $g(x)=3-x$ are
necessary and sufficient for $n=2$. The two permutations $p=(1234\ldots n)$
and $q=(12)(3)(4)\ldots (n)$ generate all the other permutations, and
adding the function $f(x)=$ if $x=2$ then 1 else $x$ gets everything else.

\vfil\end